/*
 * LinkedList.h
 *
 *  Created on: Oct 21, 2010
 *      Author: Jacob
 */

#ifndef LINKEDLIST_H_
#define LINKEDLIST_H_
#include "Node.h"
#include <string>
#include <sstream>
using std::string;
using std::ostringstream;
using std::stringstream;
#include <iostream>
using std::cout;

template<typename T>
class LinkedList
{
public:
	static LinkedList<T>* newLinkedList(bool circularlyLinked);
	void addToHead(T placeholder);
	void addToHead(Node<T>* nodeToBeAdded);
	void addToTail(T placeholder);
	void addToTail(Node<T>* nodeToBeAdded);
	void insert(T placeholder, int position);
	void insert(Node<T>* nodeToBeInserted, int position);
	void removeFromHead();
	void removeFromTail();
	void remove(int position);
	void remove(Node<T>* nodeToBeRemoved);
	Node<T>* search(T value);
	Node<T>* search(Node<T>* nodeToBeFound);
	Node<T>* getCurrent();
	void setCurrent(Node<T>* current);
	int getSize();
	string toString();
	void iterate();
	void setCurrentToHead();
	LinkedList& operator++();
	virtual ~LinkedList();
private:
	int size;
	Node<T>* head;
	Node<T>* tail;
	Node<T>* current;
	bool circularlyLinked;
	bool dummyTailRemoved;
	bool dummyHeadRemoved;
	bool overrideNullHead(Node<T>* nodeToBeAdded);
	void replaceNullHead(Node<T>* newHead);
	bool overrideNullTail(Node<T>* nodeToBeAdded);
	void replaceNullTail(Node<T>* newTail);
	void findPositionAndInsertNode(Node<T>* nodeToBeInserted, int position);
	void insertNode(Node<T>* nodeToBeInserted);
	bool removeFromHeadOrTail(int position);
	bool removeFromHeadOrTail(Node<T>* nodeToBeChedked);
	Node<T>* getNodeAtPosition(int position);
	void prepareNodeForDeletion(Node<T>* nodeToBeDeleted);
	void addNodeToHead(Node<T>* nodeToBeAdded);
	void addNodeToTail(Node<T>* nodeToBeAdded);
	void deleteNode(Node<T>* nodeToBeDeleted);
	void modifySize(int value);
	void makeListCircularlyLinked();
	Node<T>* constructNodeFromData(T placeholder);
	LinkedList(bool circularlyLinked);
};

template<typename T>
LinkedList<T>* LinkedList<T>::newLinkedList(bool circularlyLinked)
{
	return new LinkedList<T> (circularlyLinked);
}

template<typename T>
LinkedList<T>::LinkedList(bool circularlyLinked)
{
	head = new Node<T>();
	tail = new Node<T>();
	head->setNext(this->tail);
	current = head;
	size = 2;
	dummyTailRemoved = false;
	dummyHeadRemoved = false;
	this->circularlyLinked = circularlyLinked;

	if (circularlyLinked)
		tail->setNext(head);
}

template<typename T>
LinkedList<T>::~LinkedList()
{
	delete head;
}

template<typename T>
void LinkedList<T>::addToHead(T placeholder)
{
	Node<T>* newNode = constructNodeFromData(placeholder);
	addNodeToHead(newNode);
}

template<typename T>
void LinkedList<T>::addToHead(Node<T>* nodeToBeAdded)
{
	addNodeToHead(nodeToBeAdded);
}

template<typename T>
void LinkedList<T>::addNodeToHead(Node<T>* nodeToBeAdded)
{
	if (overrideNullHead(nodeToBeAdded))
		return;

	nodeToBeAdded->setNext(head);
	head = nodeToBeAdded;
	modifySize(1);
}

template<typename T>
bool LinkedList<T>::overrideNullHead(Node<T>* nodeToBeAdded)
{
	/*
	 * List is initialized with dummy head and tail
	 * When addtohead/tail is called for first time
	 * these are overwritten
	 */

	if (dummyHeadRemoved)
		return false;

	if (head->getData() == NULL)
	{
		replaceNullHead(nodeToBeAdded);
		return true;
	}

	return false;
}

template<typename T>
void LinkedList<T>::replaceNullHead(Node<T>* newHead)
{
	Node<T>* nullHead = head;
	newHead->setNext(nullHead->getNext());
	head = newHead;
	modifySize(1);
	deleteNode(nullHead);
	dummyHeadRemoved = true;
}

template<typename T>
void LinkedList<T>::addToTail(T placeholder)
{
	Node<T>* newNode = constructNodeFromData(placeholder);
	addNodeToTail(newNode);
}

template<typename T>
void LinkedList<T>::addToTail(Node<T>* nodeToBeAdded)
{
	addNodeToTail(nodeToBeAdded);
}

template<typename T>
void LinkedList<T>::addNodeToTail(Node<T>* nodeToBeAdded)
{
	if (overrideNullTail(nodeToBeAdded))
		return;

	tail->setNext(nodeToBeAdded);
	tail = nodeToBeAdded;
	makeListCircularlyLinked();
	modifySize(1);
}

template<typename T>
bool LinkedList<T>::overrideNullTail(Node<T>* nodeToBeAdded)
{
	/*
	 * List is initialized with dummy head and tail
	 * When addtohead/tail is called for first time
	 * these are overwritten
	 */

	if (dummyTailRemoved)
		return false;

	setCurrentToHead();
	for (int index = 0; index < size; index++)
	{
		if (current->getNext() == tail && tail->getData() == NULL)
		{
			replaceNullTail(nodeToBeAdded);
			return true;
		}
		++(*this);
	}

	return false;
}

template<typename T>
void LinkedList<T>::replaceNullTail(Node<T>* newTail)
{
	Node<T>* nullTail = tail;
	current->setNext(newTail);
	tail = newTail;
	modifySize(1);
	deleteNode(nullTail);
	dummyTailRemoved = true;

	if(circularlyLinked)
		makeListCircularlyLinked();
}

template<typename T>
void LinkedList<T>::insert(T placeholder, int position)
{
	Node<T>* nodeToBeInserted = constructNodeFromData(placeholder);
	this->insert(nodeToBeInserted, position);
}

template<typename T>
void LinkedList<T>::insert(Node<T>* nodeToBeInserted, int position)
{
	findPositionAndInsertNode(nodeToBeInserted, position);
}

template<typename T>
void LinkedList<T>::findPositionAndInsertNode(Node<T>* nodeToBeInserted,
		int position)
{
	setCurrentToHead();
	for (int index = 0; index < size; index++)
	{
		if (index == position)
		{
			insertNode(nodeToBeInserted);
			return;
		}
		++(*this);
	}

	//Node could not be inserted so Delete.... maybe
	delete nodeToBeInserted;
}

template<typename T>
void LinkedList<T>::insertNode(Node<T>* nodeToBeInserted)
{
	if (current == tail)
	{
		addToTail(nodeToBeInserted);
	}
	else
	{
		nodeToBeInserted->setNext(current->getNext());
		current->setNext(nodeToBeInserted);
		modifySize(1);
	}
}

template<typename T>
void LinkedList<T>::removeFromHead()
{
	Node<T>* oldHeadToBeDeleted = head;
	head = head->getNext();
	deleteNode(oldHeadToBeDeleted);
}

template<typename T>
void LinkedList<T>::removeFromTail()
{
	Node<T>* oldTailToBeDeleted = tail;
	setCurrentToHead();
	for (int index = 0; index < size; index++)
	{
		if (current->getNext() == tail)
		{
			tail = current;
			tail->setNext(NULL);
			makeListCircularlyLinked();
			deleteNode(oldTailToBeDeleted);
		}
		++(*this);
	}
}

template<typename T>
void LinkedList<T>::remove(int position)
{
	if (removeFromHeadOrTail(position))
		return;

	Node<T>* nodeToBeRemoved = getNodeAtPosition(position);

	if (nodeToBeRemoved != NULL)
	{
		prepareNodeForDeletion(nodeToBeRemoved);
	}
}

template<typename T>
void LinkedList<T>::remove(Node<T>* nodeToBeRemoved)
{
	if (removeFromHeadOrTail(nodeToBeRemoved))
		return;

	prepareNodeForDeletion(nodeToBeRemoved);
}

template<typename T>
void LinkedList<T>::prepareNodeForDeletion(Node<T>* nodeToBeDeleted)
{
	setCurrentToHead();
	for (int index = 0; index < size; index++)
	{
		if (current->getNext() == nodeToBeDeleted)
		{
			current->setNext(nodeToBeDeleted->getNext());
			deleteNode(nodeToBeDeleted);
		}

		++(*this);
	}
}

template<typename T>
bool LinkedList<T>::removeFromHeadOrTail(Node<T>* nodeToBeRemoved)
{
	if (nodeToBeRemoved == head)
	{
		removeFromHead();
		return true;
	}
	else if (nodeToBeRemoved == tail)
	{
		removeFromTail();
		return true;
	}

	return false;
}

template<typename T>
bool LinkedList<T>::removeFromHeadOrTail(int position)
{
	int headPosition = 0;

	if (position == headPosition)
	{
		removeFromHead();
		return true;
	}
	else if (position == size - 1)
	{
		removeFromTail();
		return true;
	}

	return false;
}

template<typename T>
Node<T>* LinkedList<T>::getNodeAtPosition(int position)
{
	setCurrentToHead();
	for (int index = 0; index < size; index++)
	{
		if (index == position)
		{
			return current;
		}
		++(*this);
	}

	return NULL;
}

template<typename T>
Node<T>* LinkedList<T>::search(T value)
{
	setCurrentToHead();
	for (int index = 0; index < size; index++)
	{
		if (current->getData() == value)
		{
			return current;
		}
		++(*this);
	}

	return NULL;
}

template<typename T>
Node<T>* LinkedList<T>::search(Node<T>* nodeToBeFound)
{
	setCurrentToHead();
	for (int index = 0; index < size; index++)
	{
		if (current == nodeToBeFound)
		{
			return current;
		}
		++(*this);
	}

	return NULL;
}

template<typename T>
Node<T>* LinkedList<T>::getCurrent()
{
	return this->current;
}

template<typename T>
void LinkedList<T>::setCurrent(Node<T>* current)
{
	this->current = current;
}

template<typename T>
int LinkedList<T>::getSize()
{
	return this->size;
}

template<typename T>
string LinkedList<T>::toString()
{
	ostringstream stringStream;

	setCurrentToHead();
	for (int index = 0; index < size; index++)
	{
		stringStream << "\n" << current->getData() << "    PTR: " << current;
		++(*this);
	}

	stringStream << "\n\n" << "Linked List Size: " << size;
	stringStream << "\n" << "Head: " << head->getData() << "   PTR: " << head;
	stringStream << "\n" << "Tail: " << tail->getData() << "   PTR: " << tail;

	return stringStream.str();
}

template<typename T>
void LinkedList<T>::setCurrentToHead()
{
	current = head;
}

template<typename T>
void LinkedList<T>::deleteNode(Node<T>* nodeToBeDeleted)
{
	nodeToBeDeleted->setNext(NULL);
	delete nodeToBeDeleted;
	modifySize(-1);
}

template<typename T>
void LinkedList<T>::modifySize(int value)
{
	size += value;
}

template<typename T>
void LinkedList<T>::makeListCircularlyLinked()
{
	if (circularlyLinked)
		this->tail->setNext(head);
}

template<typename T>
void LinkedList<T>::iterate()
{
	current = current->getNext();
}

template<typename T>
LinkedList<T>& LinkedList<T>::operator++()
{
	current = current->getNext();
	return *this;
}

template<typename T>
Node<T>* LinkedList<T>::constructNodeFromData(T placeholder)
{
	Node<T>* newNode = Node<T>::newNodeFromData(placeholder);
	return newNode;
}

#endif /* LINKEDLIST_H_ */
